#define DEBUG
#include <cstdio>
#include <cstring>
#include <ctime>
#include <cstdlib>

using namespace std;

typedef long long ll;
const int maxs=16;

ll mul(ll a, ll b, ll p) {
  ll ret=0;
  for (int i=0; b>>i; i++) {
    ret = (ret+a*((b>>i)&1))%p;
    a = a*2%p;
  }
  return ret;
}

ll qpower(ll a, ll n, ll p) {
  ll s=1;
  for (; n; n>>=1) {
    if (n&1) s=mul(s, a, p);
    a=mul(a, a, p);
  }
  return s;
}

bool mr(ll a) {
  const int t=8;
  const int p[t]={2, 3, 5, 7, 11, 13, 17, 19};
  if (a<2) return false;
  for (int i=0; i<t; i++) {
    if (a==p[i]) return true;
  }
  if (a<=20) return false;

  for (int i=0; i<t; i++) {
    ll x=p[i];
    if (qpower(x, a-1, a)!=1) return false;
    for (ll k=a-1, temp; k%2==0;) {
      k/=2;
      temp = qpower(x, k, a);
      if (temp==a-1) break;
      else if (temp!=1) return false;
    }
  }

  return true;
}

ll f(ll x, ll k, ll p) {
  return (mul(x, x, p)+k)%p;
}

ll gcd(ll a, ll b) {
  for (ll r=a%b; r; a=b, b=r, r=a%b);
  return b;
}

ll getFac(ll n, ll k) {
  if (n==4) {
    return 2;
  }
  ll x=rand()%n, y=x, d=1, j=0, i=1;
  for (; d==1; ) {
    x = f(x, k, n);
    d = gcd(abs(x-y), n);
    j++;
    if (i==j) y=x, i*=2;
  }
  return d==n ? 0 : d;
}

void pr(ll n, ll fac[]) {
  if (mr(n)) fac[++fac[0]] = n;
  else {
    ll temp=0;
    for (ll k=1; !(temp=getFac(n, k)); k=k%(n-1)+1);
    pr(temp, fac), pr(n/temp, fac);
  }
}

int main() {
  freopen("number.in", "r", stdin);
  freopen("number.out", "w", stdout);

  srand(time(0));

  static ll fac[maxs+1], pri[maxs+1][2], f[maxs+1][1<<maxs];
  int t;
  scanf("%d", &t);
  for (int ti=1; ti<=t; ti++) {
    ll n, p;
    scanf("%lld %lld", &n, &p);
    bool flag=true;
    if (n==1) {
      printf("1\n");
      flag = false;
    } else if (n==4) {
      printf("8\n");
      flag = false;
    } else {
      fac[0] = pri[0][0] = 0;
      pr(n, fac);
    }

    for (int i=1; flag && i<=fac[0]; i++) {
      for (int j=1; flag && j<i; j++) {
        if (fac[i]==fac[j]) {
          flag = false;
          printf("-1\n");
        }
      }
    }

    memset(f, 0, sizeof f);
    f[0][0] = 1;
    if (flag) {
      for (int i=1; i<=fac[0]; i++) {
        for (int j=0; j<(1<<fac[0]); j++) {
          for (int k=1; k<=fac[0]; k++) {
            int nj=j|(1<<(k-1));
            f[i][nj] = (f[i][nj]+mul(f[i-1][j], qpower(fac[k], fac[i]-1, p), p))%p;
          }
        }
      }
      printf("%lld\n", f[fac[0]][(1<<fac[0])-1]);
    }
  }

  fclose(stdin);
  fclose(stdout);
  return 0;
}
